#include "tree.h"

TreeNode* BuyNode(TreeDatatype ch)
{
	TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode));
	if (tmp == NULL)
	{
		perror("malloc failed !\n");
		exit(1);
	}
	tmp->data = ch;
	tmp->left = tmp->right = NULL;
	return tmp;
}

void TreePrev(TreeNode* root)
{
	//assert(root);
	if (root == NULL)
	{
		printf(" NULL");
		return;
	}
	printf("  %c ", root->data);
	TreePrev(root->left);
	TreePrev(root->right);
}

void TreeMid(TreeNode* root)
{
	if (root == NULL)
	{
		printf(" NULL  ");
		return;
	}
	TreeMid(root->left);
	printf(" %c ", root->data);
	TreeMid(root->right);
}

void TreeBack(TreeNode* root)
{
	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	TreeBack(root->left);
	TreeBack(root->right);
	printf(" %c ", root->data);
}

int TreeSize(TreeNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + TreeSize(root->left) + TreeSize(root->right);
}

int TreeLeafSize(TreeNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeKSize(TreeNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeKSize(root->left, k - 1) + TreeKSize(root->right, k - 1);
}

int TreeDepth(TreeNode* root)
{
	if (root == NULL)
		return 0;
	int left = TreeDepth(root->left);
	int right = TreeDepth(root->right);
	return 1+(left < right ? right : left);
}

TreeNode* TreePrev_1(TreeNode* root, TreeDatatype x)
{
	if (root == NULL)
	{
		printf(" NULL");
		return;
	}
	if (root->data == x)
		return root;
	TreePrev(root->left);
	TreePrev(root->right);
}


TreeNode* TreeNodeFind(TreeNode* root, TreeDatatype x)
{
	TreePrev_1(root, x);
	return NULL;
}

void TreeDestroy(TreeNode* *root)
{
	//assert(root);
	if (*root == NULL)
	{
		return;
	}
	free(*root);
	TreeDestroy(&((*root)->left));
	TreeDestroy(&((*root)->right));
	*root = NULL;
}